Maximal square

Time: O(N^2); Space: O(N); medium

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

Example 1:

Input: matrix =

[
    ['1', '0', '1', '0', '0'],
    ['1', '0', '1', '1', '1'],
    ['1', '1', '1', '1', '1'],
    ['1', '0', '0', '1', '0']
]

Output: 4

Example 2:

Input: matrix =

[
  ['0', '0', '0'],
  ['1', '1', '1']
]

Output: 1

class Solution1(object):
    """
    Time: O(N^2)
    Space: O(N)
    """
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if not matrix:
            return 0

        m, n = len(matrix), len(matrix[0])
        size = [[0 for j in range(n)] for i in range(2)]
        max_size = 0

        for j in range(n):
            if matrix[0][j] == '1':
                size[0][j] = 1
            max_size = max(max_size, size[0][j])

        for i in range(1, m):
            if matrix[i][0] == '1':
                size[i % 2][0] = 1
            else:
                size[i % 2][0] = 0
            for j in range(1, n):
                if matrix[i][j] == '1':
                    size[i % 2][j] = min(size[i % 2][j - 1], \
                    size[(i - 1) % 2][j], \
                    size[(i - 1) % 2][j - 1]) + 1
                    max_size = max(max_size, size[i % 2][j])
                else:
                    size[i % 2][j] = 0

        return max_size * max_size

s = Solution1()

matrix = [
        ['1', '0', '1', '0', '0'],
        ['1', '0', '1', '1', '1'],
        ['1', '1', '1', '1', '1'],
        ['1', '0', '0', '1', '0']
    ]
assert s.maximalSquare(matrix) == 4

matrix = [
  ['0', '0', '0'],
  ['1', '1', '1']
]
assert s.maximalSquare(matrix) == 1

2. Dynamic Programming

class Solution2(object):
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if not matrix:
            return 0

        m, n = len(matrix), len(matrix[0])
        size = [[0 for j in range(n)] for i in range(m)]
        max_size = 0

        for j in range(n):
            if matrix[0][j] == '1':
                size[0][j] = 1
            max_size = max(max_size, size[0][j])

        for i in range(1, m):
            if matrix[i][0] == '1':
                size[i][0] = 1
            else:
                size[i][0] = 0

            for j in range(1, n):
                if matrix[i][j] == '1':
                    size[i][j] = min(size[i][j - 1], \
                    size[i - 1][j], \
                    size[i - 1][j - 1]) + 1
                    max_size = max(max_size, size[i][j])
                else:
                    size[i][j] = 0

        return max_size * max_size

s = Solution2()

matrix = [
        ['1', '0', '1', '0', '0'],
        ['1', '0', '1', '1', '1'],
        ['1', '1', '1', '1', '1'],
        ['1', '0', '0', '1', '0']
    ]
assert s.maximalSquare(matrix) == 4

matrix = [
  ['0', '0', '0'],
  ['1', '1', '1']
]
assert s.maximalSquare(matrix) == 1

3. Dynamic Programming

class Solution3(object):
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if not matrix:
            return 0

        H, W = 0, 1
        # DP table stores (h, w) for each (i, j).
        table = [[[0, 0] for j in range(len(matrix[0]))] \
                         for i in range(len(matrix))]

        for i in reversed(range(len(matrix))):
            for j in reversed(range(len(matrix[i]))):
                # Find the largest h such that (i, j) to (i + h - 1, j) are feasible.
                # Find the largest w such that (i, j) to (i, j + w - 1) are feasible.
                if matrix[i][j] == '1':
                    h, w = 1, 1
                    if i + 1 < len(matrix):
                        h = table[i + 1][j][H] + 1
                    if j + 1 < len(matrix[i]):
                        w = table[i][j + 1][W] + 1
                    table[i][j] = [h, w]

        # A table stores the length of largest square for each (i, j).
        s = [[0 for j in range(len(matrix[0]))] \
                for i in range(len(matrix))]

        max_square_area = 0
        for i in reversed(range(len(matrix))):
            for j in reversed(range(len(matrix[i]))):
                side = min(table[i][j][H], table[i][j][W])
                if matrix[i][j] == '1':
                    # Get the length of largest square with bottom-left corner (i, j).
                    if i + 1 < len(matrix) and j + 1 < len(matrix[i + 1]):
                        side = min(s[i + 1][j + 1] + 1, side)
                    s[i][j] = side
                    max_square_area = max(max_square_area, side * side)

        return max_square_area

s = Solution3()

matrix = [
        ['1', '0', '1', '0', '0'],
        ['1', '0', '1', '1', '1'],
        ['1', '1', '1', '1', '1'],
        ['1', '0', '0', '1', '0']
    ]
assert s.maximalSquare(matrix) == 4

matrix = [
  ['0', '0', '0'],
  ['1', '1', '1']
]
assert s.maximalSquare(matrix) == 1

4. Brute Force [O((MxN)^2, O(1)]

The simplest approach consists of trying to find out every possible square of 1’s that can be formed from within the matrix. The question now is – how to go for it?

We use a variable to contain the size of the largest square found so far and another variable to store the size of the current, both initialized to 0. Starting from the left uppermost point in the matrix, we search for a 1. No operation needs to be done for a 0. Whenever a 1 is found, we try to find out the largest square that can be formed including that 1. For this, we move diagonally (right and downwards), i.e. we increment the row index and column index temporarily and then check whether all the elements of that row and column are 1 or not. If all the elements happen to be 1, we move diagonally further as previously. If even one element turns out to be 0, we stop this diagonal movement and update the size of the largest square. Now we, continue the traversal of the matrix from the element next to the initial 1 found, till all the elements of the matrix have been traversed.

5. Dynamic Programming [O(MxN), O(MxN)]

Algorithm

We will explain this approach with the help of an example.

0 1 1 1 0
1 1 1 1 1
0 1 1 1 1
0 1 1 1 1
0 0 1 1 1

We initialize another matrix (dp) with the same dimensions as the original one initialized with all 0’s.

dp(i,j) represents the side length of the maximum square whose bottom right corner is the cell with index (i,j) in the original matrix.

Starting from index (0,0), for every 1 found in the original matrix, we update the value of the current element as

dp(i, j) = min(dp(i-1, j), dp(i-1, j-1), d(i, j-1)) + 1

We also remember the size of the largest square found so far. In this way, we traverse the original matrix once and find out the required maximum size. This gives the side length of the square (say maxsqlenmaxsqlen). The required result is the area maxsqlen^2

To understand how this solution works, see the figure below.

An entry 2 at (1, 3) implies that we have a square of side 2 up to that index in the original matrix. Similarly, a 2 at (1, 2) and (2, 2) implies that a square of side 2 exists up to that index in the original matrix. Now to make a square of side 3, only a single entry of 1 is pending at (2, 3). So, we enter a 3 corresponding to that position in the dp array.

Now consider the case for the index (3, 4). Here, the entries at index (3, 3) and (2, 3) imply that a square of side 3 is possible up to their indices. But, the entry 1 at index (2, 4) indicates that a square of side 1 only can be formed up to its index. Therefore, while making an entry at the index (3, 4), this element obstructs the formation of a square having a side larger than 2. Thus, the maximum sized square that can be formed up to this index is of size 2×2.

6. Better Dynamic Programming [O(MxN), O(N)]

Algorithm

In the previous approach for calculating dp of i-th row we are using only the previous element and the (i-1)-th row.

Therefore, we don’t need 2D dp matrix as 1D dp array will be sufficient for this.

Initially the dp array contains all 0’s. As we scan the elements of the original matrix across a row, we keep on updating the dp array as per the equation dp[j]=min(dp[j-1],dp[j],prev), where prev refers to the old dp[j-1]. For every row, we repeat the same process and update in the same dp array.

See also:

https://leetcode.com/problems/maximal-square

https://www.lintcode.com/problem/maximal-square/description

Related problems:

https://leetcode.com/problems/maximal-rectangle/

https://leetcode.com/problems/largest-plus-sign/

https://www.lintcode.com/problem/maximal-square-ii

https://www.lintcode.com/problem/sum-of-square-numbers